import collections
import heapq


class Solution(object):
    def maxProbability(self, n, edges, succProb, start, end):
        d = collections.defaultdict(dict)
        for index, (u, v) in enumerate(edges):
            d[u][v] = succProb[index]
            d[v][u] = succProb[index]
        p = [-1] * n
        st = [[-1, start]]
        while st:
            while st and p[st[0][1]] >= 0:
                heapq.heappop(st)
            if st:
                dist, index = heapq.heappop(st)
                p[index] = - dist
                for v in d[index]:
                    heapq.heappush(st, [- p[index] * d[index][v], v])
        return max(p[end], 0)
